package main

import "fmt"

//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//
// 算法的时间复杂度应该为 O(log (m+n)) 。
//
//
//
// 示例 1：
//
//
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
//
//
// 示例 2：
//
//
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
//
//
//
//
//
//
// 提示：
//
//
// nums1.length == m
// nums2.length == n
// 0 <= m <= 1000
// 0 <= n <= 1000
// 1 <= m + n <= 2000
// -10⁶ <= nums1[i], nums2[i] <= 10⁶
//
// Related Topics 数组 二分查找 分治 👍 4980 👎 0
func main() {
	fmt.Println(findMedianSortedArrays([]int{1, 3}, []int{2}))
	fmt.Println(findMedianSortedArrays([]int{1, 2}, []int{3, 4}))
	fmt.Println(findMedianSortedArrays([]int{1}, []int{2,3}))
}

//leetcode submit region begin(Prohibit modification and deletion)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	var m1, m2 int

	if isOdd(len(nums1) + len(nums2)) {
		for i := 0; i < (len(nums1) + len(nums2)) / 2; i++ {
			if m1 >= len(nums1) {
				m2++
				continue
			} else if m2 >= len(nums2) {
				m1++
				continue
			}
			if nums2[m2] > nums1[m1] {
				m1++
			} else {
				m2++
			}
		}
		if m1 >= len(nums1) {
			return float64(nums2[m2])
		} else if m2 >= len(nums2) {
			return float64(nums1[m1])
		} else {
			return float64(min(nums1[m1], nums2[m2]))
		}
	} else {
		// 获取两个值
		// 第 (len(nums1) + len(nums2)) / 2 - 1 和 (len(nums1) + len(nums2)) / 2
		var tmp1, tmp2 int
		for i := 0; i < len(nums1) + len(nums2); i++ {
			if i == (len(nums1) + len(nums2)) / 2 - 1 {
				if m1 >= len(nums1) {
					tmp1 = nums2[m2]
				} else if m2 >= len(nums2) {
					tmp1 = nums1[m1]
				} else {
					tmp1 = min(nums1[m1], nums2[m2])
				}
			}
			if i == (len(nums1) + len(nums2)) / 2 {
				if m1 >= len(nums1) {
					tmp2 = nums2[m2]
				} else if m2 >= len(nums2) {
					tmp2 = nums1[m1]
				} else {
					tmp2 = min(nums1[m1], nums2[m2])
				}
				break
			}
			if m1 >= len(nums1) {
				m2++
				continue
			} else if m2 >= len(nums2) {
				m1++
				continue
			}
			if nums2[m2] > nums1[m1] {
				m1++
			} else {
				m2++
			}
		}
		return float64(tmp1 + tmp2) / float64(2)
	}
}

func isOdd(l int) bool {
	return (l / 2) * 2 != l
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}
//leetcode submit region end(Prohibit modification and deletion)

